In a processing system, a plurality of devices, such as processors and information input and output units, often share use of a common resource, for example a communication bus or a system memory. Only one of the devices can generally make use of the shared resource at any one time, and hence it is necessary to coordinate use of the shared resource between the using devices and to arbitrate between multiple requests to use the shared resource.
A common technique for arbitrating access to a resource is the daisy-chain arbitration scheme. In this scheme, whenever a using device wishes to access the shared resource, it issues an access request to an arbitrator. The arbitrator receives the access requests from the using devices and in response, whenever it finds the resource free for use by a device, it issues an access grant signal to the using devices. The using devices are connected in series, i.e., in a chain, by the grant signal line and the grant signal is daisy-chained through the using devices. When the grant signal is received by a device that does not have a request for access pending, the device merely passes the grant signal down the grant signal line to the next device in the chain. When the grant signal is received by a device that has a request for access pending, the device keeps, or blocks, the access grant signal--does not propagate it on to the next device in the chain. Then the device that kept the access grant signal accesses the resource and cancels its resource access request.
While the daisy-chain arbitration scheme as described is simple and effective, it does suffer from certain disadvantages. For example, the scheme gives priority of access to devices at the head of the chain over devices further along in the chain, and thus it is possible that one or more devices at the end of the chain will be locked out, prevented from accessing the shared resource, by frequent accesses made by the preceding devices in the chain. Thus certain devices may be effectively prevented from ever accessing the shared resource.
Furthermore, problems may arise when a device issues a request for access to the shared resource at substantially the same time that it receives an access grant signal intended for a requesting device further down the chain. This situation may result in glitches--oscillations of signal values--on the grant signal line such as will cause both the device under consideration as well as the subsequent device in the chain to receive a grant signal, resulting in both devices attempting to access the resource simultaneously. Prior art attempts at solving this problem, such as synchronizing the issuance of access requests with receipt of access grant signals at each using device to ensure that they do not occur simultaneously, or sampling the access grant line multiple times at each device to ensure that a grant signal has truly been received, introduce too much additional circuitry and time delay into the arbitration scheme and thereby adversely affect system cost and performance.